class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        sDict = {}
        for c in t:
            if c not in sDict:
                sDict.update({c:0})
            sDict[c]+=1
        a, b = 0, 0
        bestA, bestB = len(s)-1, 0
        nAlpha = len(sDict)
        while nAlpha>0 and b<len(s):
            c = s[b]
            if c in sDict:
                sDict[c]-=1
                if sDict[c]==0:
                    nAlpha-=1
            b+=1
        if nAlpha>0:return""
        bestA, bestB = a, b

        while b<len(s) or a<b:
            need = None
            while a<b:
                c = s[a]
                a+=1
                if c in sDict: 
                    sDict[c]+=1
                    if sDict[c]>0:
                        need = c
                        break
            if b-(a-1)<bestB-bestA:
                bestA, bestB = a-1,b
            while b<len(s):
                c = s[b]
                b+=1
                if c in sDict:
                    sDict[c]-=1
                    if c==need:
                        need=None
                        break
            if b==len(s) and need: break
            if b-a<bestB-bestA:
                bestA,bestB=a,b
        return s[bestA:bestB]

print(Solution().minWindow("ADOBECODEBANC", "ABC"))
